# $Id: tree.py 9227e81e919a 2012/08/27 15:49:57 pgurumur $
# Copyright (c) 2009 Prabhu Gurumurthy  <pgurumur@gmail.com>
# 
# Permission to use, copy, modify, and distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
#

__version__  = "$Revision: 9227e81e919a $"
__author__   = "$Author: pgurumur $"
__modified__ = "$Date: 2012-08-27 15:49:57Z $"

LEFT = 1
RIGHT = 2

class Node(object):
   def __init__(self, Key = None):
      super(Node, self).__init__()
      self._key = Key
      self._red = False
      self._left = None
      self._right = None
      self._parent = None

   def __str__(self):
      return str(self.key)

   def __repr__(self):
      return str(self)

   key = property(fget = lambda self: self._key)
   right = property(fget = lambda self: self._right)
   left = property(fget = lambda self: self._left)
   red = property(fget = lambda self: self._red)
   parent = property(fget = lambda self: self._parent)

class Tree(object):
   def __init__(self, create = Node):
      super(Tree, self).__init__()
      self._nil = create()
      self._root = self.nil
      self._create = create

   root = property(fget = lambda self: self._root)
   nil = property(fget = lambda self: self._nil)

   def search(self, key, root = None):
      if not root:
         root = self.root

      while root != self.nil and key != root.key:
         print(key)
         if key < root.key:
            root = root.left
         else:
            root = root.right

         print("key", root.key)

      return root

   def minimum(self, root = None):
      if not root:
         root = self.root

      while root.left and root.left != self.nil:
         root = root.left

      return root

   def maximum(self, root = None):
      if not root:
         root = self.root

      while root.right and root.right != self.nil:
         root = root.right

      return root

   def insertkey(self, key):
      self.insert(self.create(key))

   def insert(self, node):
      jy = self.nil
      ix = self.root

      while ix != self.nil:
         jy = ix
         if node.key < ix.key:
            ix = ix.left
         else:
            ix = ix.right

      node._parent = jy
      if jy == self.nil:
         self._root = node
      elif node.key < jy.key:
         jy._left = node
      else:
         jy._right = node

      node._left = self.nil
      node._right = self.nil
      node._red = True

      self._fixup(node)
      print(node.key)

   def _fixup(self, node):
      while node.parent.red:
         if node.parent == node.parent.parent.left:
            jy = node.parent.parent.right
            if jy.red:
               node.parent._red = False
               jy._red = False
               node.parent.parent._red = True
               node = node.parent.parent
            else:
               if node == node.parent.right:
                  node = node.parent
                  self._rotate(node, LEFT)

               node.parent._red = False
               node.parent.parent._red = True
               self._rotate(node.parent.parent, RIGHT)
         else:
            jy = node.parent.parent.left
            if jy.red:
               node.parent._red = False
               jy._red = False
               node.parent.parent._red = True
               node = node.parent.parent
            else:
               if node == node.parent.left:
                  node = node.parent
                  self._rotate(node, RIGHT)

               node.parent._red = False
               node.parent.parent._red = True
               self._rotate(node.parent.parent, LEFT)

      self.root._red = False

   def _rotate(self, node, direction = 0):
      if direction == LEFT:
         jy = node.right
         node._right = jy.left
         if jy.left != self.nil:
            jy.left._parent = node

         jy._parent = node.parent
         if node.parent == self.nil:
            self._root = jy
         elif node == node.parent.left:
            node.parent._left = jy
         else:
            node.parent._right = jy

         jy._left = node
         node._parent = jy
      elif direction == RIGHT:
         ix = node.left
         node._left = ix.right
         if ix.right != self.nil:
            ix.right._parent = node

         ix._parent = node.parent
         if node.parent == self.nil:
            self._root = ix
         elif node == node.parent.right:
            node.parent._right = ix
         else:
            node.parent._left = ix

         ix._right = node
         node._parent = ix

   def check(self):
      numblack, isok = redOrBlack(self.root)
      return isok and not self.root._red

   def redOrBlack(self, node):
      if (node.left and not node.right) or (node.right and not node.left):
         return 0, False

      if not node.left and not node.right and node.red:
         return 0, False

      if node.red and node.left and node.right:
         if node.left.red or node.right.red:
            return 0, False

      if node.left and node.right:
         if self.nil != node.left and node != node.left.parent:
            return 0, False

         if self.nil != node.right and node != node.right.parent:
            return 0, False

         left, leftok = redOrBlack(node.left)
         if not leftok:
            return 0, False

         right, rightok = redOrBlack(node.right)
         if not rightok:
            return 0, False

         if left != right:
            return 0, False

         return left, True
      else:
         return 0, True
